package dataStructure.tree;

/**
 * @author lhn
 * @date 2024-09-03 9:44
 */

public class BinaryTreeDemo {

    public static void main(String[] args) {
        BinaryTree_ binaryTree = new BinaryTree_();
        HeroNode root = new HeroNode(1,"宋江");
        HeroNode heroNode1 = new HeroNode(2,"吴用");
        HeroNode heroNode2 = new HeroNode(3,"卢俊义");
        HeroNode heroNode3 = new HeroNode(4,"林冲");
        HeroNode heroNode4 = new HeroNode(5,"鲁智深");
        HeroNode heroNode5 = new HeroNode(6,"关胜");

        binaryTree.setRoot(root);
        root.setLeft(heroNode1);
        root.setRight(heroNode2);
        heroNode2.setRight(heroNode3);
        heroNode2.setLeft(heroNode4);
        heroNode1.setLeft(heroNode5);

        System.out.println("前序遍历:");
        binaryTree.preOrder();

//        System.out.println("中序遍历:");
//        binaryTree.inOrder();
//
//        System.out.println("后序遍历:");
//        binaryTree.postOrder();
//
//        System.out.println("前序查找:");
//        System.out.println("前序查找结果：" + binaryTree.preOrderFindNode(5));
//        System.out.println("前序查找结果：" + binaryTree.preFindNode(6));

//        System.out.println("中序查找:");
//        System.out.println("中序查找结果：" + binaryTree.inOrderFindNode(5));
//
//        System.out.println("后序查找:");
//        System.out.println("后序查找结果：" + binaryTree.postOrderFindNode(5));

        System.out.println("删除节点: ");
        System.out.println(binaryTree.delNode(3));

        binaryTree.preOrder();

    }

}
class BinaryTree_ {
    private HeroNode root;
    public void setRoot(HeroNode root) {
        this.root = root;
    }
    public HeroNode getRoot() {
        return root;
    }
    //前序遍历
    public void preOrder() {
        if (this.root != null) {
            this.root.preOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    //中序遍历
    public void inOrder() {
        if (this.root != null) {
            this.root.inOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    //后序遍历
    public void postOrder() {
        if (this.root != null) {
            this.root.postOrder();
        } else {
            System.out.println("二叉树为空，无法遍历");
        }
    }

    public HeroNode preOrderFindNode(int no) {
        if (this.root != null) {
            return this.root.preOrderFindNode(no);
        } else {
            System.out.print("二叉树为空，无法查找 ");
            return null;
        }
    }

    public HeroNode inOrderFindNode(int no) {
        if (this.root != null) {
            return this.root.inOrderFindNode(no);
        } else {
            System.out.print("二叉树为空，无法查找 ");
            return null;
        }
    }

    public HeroNode postOrderFindNode(int no) {
        if (this.root != null) {
            return this.root.postOrderFindNode(no);
        } else {
            System.out.print("二叉树为空，无法查找 ");
            return null;
        }
    }

    public boolean delNode(int no) {
        if (this.root != null) {
            if (this.root.getNo() == no) {
                this.root = null;
                return true;
            } else {
                return this.root.delNode(no);
            }
        } else {
            System.out.print("二叉树为空，无法删除 ");
            return false;
        }
    }

}

class HeroNode {
    private int no; //编号
    private String name;    //名字
    private HeroNode left;
    private HeroNode right;

    public HeroNode() {
    }

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    //前序遍历
    public void preOrder() {
        System.out.println(this);
        if (this.left != null) {
            this.left.preOrder();
        }
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    //中序遍历
    public void inOrder() {
        if (this.left != null) {
            this.left.inOrder();
        }
        System.out.println(this);
        if (this.right != null) {
            this.right.inOrder();
        }
    }

    //后序遍历
    public void postOrder() {
        if (this.left != null) {
            this.left.postOrder();
        }
        if (this.right != null) {
            this.right.postOrder();
        }
        System.out.println(this);
    }

    //前序查找
    public HeroNode preOrderFindNode(int no) {
        System.out.println("进入前序查找");
        if (this.no == no) {
            return this;
        }
        HeroNode resNode = null;
        //左递归查找
        if (this.left != null) {
            resNode = this.getLeft().preOrderFindNode(no);
        }
        if (resNode != null) {
            return resNode;
        }
        //右递归查找
        if (this.right != null) {
            resNode = this.getRight().preOrderFindNode(no);
        }
        if (resNode != null) {
            return resNode;
        }
        return resNode;
    }

    //中序查找
    public HeroNode inOrderFindNode(int no) {

        HeroNode resNode = null;
        //左递归查找
        if (this.left != null) {
            resNode = this.getLeft().inOrderFindNode(no);
        }
        if (resNode != null) {
            return resNode;
        }
        System.out.println("进入中序查找");
        if (this.no == no) {
            return this;
        }
        //右递归查找
        if (this.right != null) {
            resNode = this.getRight().inOrderFindNode(no);
        }
        if (resNode != null) {
            return resNode;
        }
        return resNode;
    }

    public HeroNode postOrderFindNode(int no) {

        HeroNode resNode = null;
        //左递归查找
        if (this.left != null) {
            resNode = this.getLeft().postOrderFindNode(no);
        }
        if (resNode != null) {
            return resNode;
        }
        //右递归查找
        if (this.right != null) {
            resNode = this.getRight().postOrderFindNode(no);
        }
        if (resNode != null) {
            return resNode;
        }
        System.out.println("进入后序查找" + this.getNo() );
        if (this.no == no) {
            return this;
        }
        return resNode;
    }

    //递归删除节点
    //1.需求：如果要删除的节点是叶子节点，则删除该节点
    //2.如果要删除的节点是非叶子节点，则删除该子树
    public boolean delNode(int no) {
        System.out.println("进入删除节点" + this.getNo());
        //如果当前节点的左子节点不为空，并且左子节点的编号等于要删除的节点的编号，则删除
        if (this.left != null && this.left.no == no) {
            this.left = null;
            return true;
        }
        //右同理
        if (this.right != null && this.right.no == no) {
            this.right = null;
            return true;
        }
        //如果左右子树都不为空，则继续递归
//        if (this.left != null) {
//            //如果左递归删除成功，则返回true;删除失败，则继续右递归
//            if (this.left.delNode(no)==true) {
//                return true;
//            } else {
//                return this.right.delNode(no);
//            }
//        } else if (this.right != null) {
//            return this.left.delNode(no);
//        }

        // 递归地在左子树中查找并尝试删除节点
        if (this.left != null && this.left.delNode(no)) {
            return true; // 左子树中删除了节点，递归成功
        }

        // 如果左子树中没有删除节点，继续在右子树中查找并尝试删除节点
        if (this.right != null && this.right.delNode(no)) {
            return true; // 右子树中删除了节点，递归成功
        }
        return false;
    }

}